home *** CD-ROM | disk | FTP | other *** search
/ Freelog 100 / FreelogNo100-NovembreDecembre2010.iso / Musique / solfege / solfege-win32-3.17.0.exe / {app} / bin / Lib / compiler / pyassem.py < prev    next >
Text File  |  2006-03-10  |  27KB  |  819 lines
  1. """A flow graph representation for Python bytecode"""
  2.  
  3. import dis
  4. import new
  5. import sys
  6.  
  7. from compiler import misc
  8. from compiler.consts \
  9.      import CO_OPTIMIZED, CO_NEWLOCALS, CO_VARARGS, CO_VARKEYWORDS
  10.  
  11. class FlowGraph:
  12.     def __init__(self):
  13.         self.current = self.entry = Block()
  14.         self.exit = Block("exit")
  15.         self.blocks = misc.Set()
  16.         self.blocks.add(self.entry)
  17.         self.blocks.add(self.exit)
  18.  
  19.     def startBlock(self, block):
  20.         if self._debug:
  21.             if self.current:
  22.                 print "end", repr(self.current)
  23.                 print "    next", self.current.next
  24.                 print "   ", self.current.get_children()
  25.             print repr(block)
  26.         self.current = block
  27.  
  28.     def nextBlock(self, block=None):
  29.         # XXX think we need to specify when there is implicit transfer
  30.         # from one block to the next.  might be better to represent this
  31.         # with explicit JUMP_ABSOLUTE instructions that are optimized
  32.         # out when they are unnecessary.
  33.         #
  34.         # I think this strategy works: each block has a child
  35.         # designated as "next" which is returned as the last of the
  36.         # children.  because the nodes in a graph are emitted in
  37.         # reverse post order, the "next" block will always be emitted
  38.         # immediately after its parent.
  39.         # Worry: maintaining this invariant could be tricky
  40.         if block is None:
  41.             block = self.newBlock()
  42.  
  43.         # Note: If the current block ends with an unconditional
  44.         # control transfer, then it is incorrect to add an implicit
  45.         # transfer to the block graph.  The current code requires
  46.         # these edges to get the blocks emitted in the right order,
  47.         # however. :-(  If a client needs to remove these edges, call
  48.         # pruneEdges().
  49.  
  50.         self.current.addNext(block)
  51.         self.startBlock(block)
  52.  
  53.     def newBlock(self):
  54.         b = Block()
  55.         self.blocks.add(b)
  56.         return b
  57.  
  58.     def startExitBlock(self):
  59.         self.startBlock(self.exit)
  60.  
  61.     _debug = 0
  62.  
  63.     def _enable_debug(self):
  64.         self._debug = 1
  65.  
  66.     def _disable_debug(self):
  67.         self._debug = 0
  68.  
  69.     def emit(self, *inst):
  70.         if self._debug:
  71.             print "\t", inst
  72.         if inst[0] in ['RETURN_VALUE', 'YIELD_VALUE']:
  73.             self.current.addOutEdge(self.exit)
  74.         if len(inst) == 2 and isinstance(inst[1], Block):
  75.             self.current.addOutEdge(inst[1])
  76.         self.current.emit(inst)
  77.  
  78.     def getBlocksInOrder(self):
  79.         """Return the blocks in reverse postorder
  80.  
  81.         i.e. each node appears before all of its successors
  82.         """
  83.         # XXX make sure every node that doesn't have an explicit next
  84.         # is set so that next points to exit
  85.         for b in self.blocks.elements():
  86.             if b is self.exit:
  87.                 continue
  88.             if not b.next:
  89.                 b.addNext(self.exit)
  90.         order = dfs_postorder(self.entry, {})
  91.         order.reverse()
  92.         self.fixupOrder(order, self.exit)
  93.         # hack alert
  94.         if not self.exit in order:
  95.             order.append(self.exit)
  96.  
  97.         return order
  98.  
  99.     def fixupOrder(self, blocks, default_next):
  100.         """Fixup bad order introduced by DFS."""
  101.  
  102.         # XXX This is a total mess.  There must be a better way to get
  103.         # the code blocks in the right order.
  104.  
  105.         self.fixupOrderHonorNext(blocks, default_next)
  106.         self.fixupOrderForward(blocks, default_next)
  107.  
  108.     def fixupOrderHonorNext(self, blocks, default_next):
  109.         """Fix one problem with DFS.
  110.  
  111.         The DFS uses child block, but doesn't know about the special
  112.         "next" block.  As a result, the DFS can order blocks so that a
  113.         block isn't next to the right block for implicit control
  114.         transfers.
  115.         """
  116.         index = {}
  117.         for i in range(len(blocks)):
  118.             index[blocks[i]] = i
  119.  
  120.         for i in range(0, len(blocks) - 1):
  121.             b = blocks[i]
  122.             n = blocks[i + 1]
  123.             if not b.next or b.next[0] == default_next or b.next[0] == n:
  124.                 continue
  125.             # The blocks are in the wrong order.  Find the chain of
  126.             # blocks to insert where they belong.
  127.             cur = b
  128.             chain = []
  129.             elt = cur
  130.             while elt.next and elt.next[0] != default_next:
  131.                 chain.append(elt.next[0])
  132.                 elt = elt.next[0]
  133.             # Now remove the blocks in the chain from the current
  134.             # block list, so that they can be re-inserted.
  135.             l = []
  136.             for b in chain:
  137.                 assert index[b] > i
  138.                 l.append((index[b], b))
  139.             l.sort()
  140.             l.reverse()
  141.             for j, b in l:
  142.                 del blocks[index[b]]
  143.             # Insert the chain in the proper location
  144.             blocks[i:i + 1] = [cur] + chain
  145.             # Finally, re-compute the block indexes
  146.             for i in range(len(blocks)):
  147.                 index[blocks[i]] = i
  148.  
  149.     def fixupOrderForward(self, blocks, default_next):
  150.         """Make sure all JUMP_FORWARDs jump forward"""
  151.         index = {}
  152.         chains = []
  153.         cur = []
  154.         for b in blocks:
  155.             index[b] = len(chains)
  156.             cur.append(b)
  157.             if b.next and b.next[0] == default_next:
  158.                 chains.append(cur)
  159.                 cur = []
  160.         chains.append(cur)
  161.  
  162.         while 1:
  163.             constraints = []
  164.  
  165.             for i in range(len(chains)):
  166.                 l = chains[i]
  167.                 for b in l:
  168.                     for c in b.get_children():
  169.                         if index[c] < i:
  170.                             forward_p = 0
  171.                             for inst in b.insts:
  172.                                 if inst[0] == 'JUMP_FORWARD':
  173.                                     if inst[1] == c:
  174.                                         forward_p = 1
  175.                             if not forward_p:
  176.                                 continue
  177.                             constraints.append((index[c], i))
  178.  
  179.             if not constraints:
  180.                 break
  181.  
  182.             # XXX just do one for now
  183.             # do swaps to get things in the right order
  184.             goes_before, a_chain = constraints[0]
  185.             assert a_chain > goes_before
  186.             c = chains[a_chain]
  187.             chains.remove(c)
  188.             chains.insert(goes_before, c)
  189.  
  190.         del blocks[:]
  191.         for c in chains:
  192.             for b in c:
  193.                 blocks.append(b)
  194.  
  195.     def getBlocks(self):
  196.         return self.blocks.elements()
  197.  
  198.     def getRoot(self):
  199.         """Return nodes appropriate for use with dominator"""
  200.         return self.entry
  201.  
  202.     def getContainedGraphs(self):
  203.         l = []
  204.         for b in self.getBlocks():
  205.             l.extend(b.getContainedGraphs())
  206.         return l
  207.  
  208. def dfs_postorder(b, seen):
  209.     """Depth-first search of tree rooted at b, return in postorder"""
  210.     order = []
  211.     seen[b] = b
  212.     for c in b.get_children():
  213.         if seen.has_key(c):
  214.             continue
  215.         order = order + dfs_postorder(c, seen)
  216.     order.append(b)
  217.     return order
  218.  
  219. class Block:
  220.     _count = 0
  221.  
  222.     def __init__(self, label=''):
  223.         self.insts = []
  224.         self.inEdges = misc.Set()
  225.         self.outEdges = misc.Set()
  226.         self.label = label
  227.         self.bid = Block._count
  228.         self.next = []
  229.         Block._count = Block._count + 1
  230.  
  231.     def __repr__(self):
  232.         if self.label:
  233.             return "<block %s id=%d>" % (self.label, self.bid)
  234.         else:
  235.             return "<block id=%d>" % (self.bid)
  236.  
  237.     def __str__(self):
  238.         insts = map(str, self.insts)
  239.         return "<block %s %d:\n%s>" % (self.label, self.bid,
  240.                                        '\n'.join(insts))
  241.  
  242.     def emit(self, inst):
  243.         op = inst[0]
  244.         if op[:4] == 'JUMP':
  245.             self.outEdges.add(inst[1])
  246.         self.insts.append(inst)
  247.  
  248.     def getInstructions(self):
  249.         return self.insts
  250.  
  251.     def addInEdge(self, block):
  252.         self.inEdges.add(block)
  253.  
  254.     def addOutEdge(self, block):
  255.         self.outEdges.add(block)
  256.  
  257.     def addNext(self, block):
  258.         self.next.append(block)
  259.         assert len(self.next) == 1, map(str, self.next)
  260.  
  261.     _uncond_transfer = ('RETURN_VALUE', 'RAISE_VARARGS', 'YIELD_VALUE',
  262.                         'JUMP_ABSOLUTE', 'JUMP_FORWARD', 'CONTINUE_LOOP')
  263.  
  264.     def pruneNext(self):
  265.         """Remove bogus edge for unconditional transfers
  266.  
  267.         Each block has a next edge that accounts for implicit control
  268.         transfers, e.g. from a JUMP_IF_FALSE to the block that will be
  269.         executed if the test is true.
  270.  
  271.         These edges must remain for the current assembler code to
  272.         work. If they are removed, the dfs_postorder gets things in
  273.         weird orders.  However, they shouldn't be there for other
  274.         purposes, e.g. conversion to SSA form.  This method will
  275.         remove the next edge when it follows an unconditional control
  276.         transfer.
  277.         """
  278.         try:
  279.             op, arg = self.insts[-1]
  280.         except (IndexError, ValueError):
  281.             return
  282.         if op in self._uncond_transfer:
  283.             self.next = []
  284.  
  285.     def get_children(self):
  286.         if self.next and self.next[0] in self.outEdges:
  287.             self.outEdges.remove(self.next[0])
  288.         return self.outEdges.elements() + self.next
  289.  
  290.     def getContainedGraphs(self):
  291.         """Return all graphs contained within this block.
  292.  
  293.         For example, a MAKE_FUNCTION block will contain a reference to
  294.         the graph for the function body.
  295.         """
  296.         contained = []
  297.         for inst in self.insts:
  298.             if len(inst) == 1:
  299.                 continue
  300.             op = inst[1]
  301.             if hasattr(op, 'graph'):
  302.                 contained.append(op.graph)
  303.         return contained
  304.  
  305. # flags for code objects
  306.  
  307. # the FlowGraph is transformed in place; it exists in one of these states
  308. RAW = "RAW"
  309. FLAT = "FLAT"
  310. CONV = "CONV"
  311. DONE = "DONE"
  312.  
  313. class PyFlowGraph(FlowGraph):
  314.     super_init = FlowGraph.__init__
  315.  
  316.     def __init__(self, name, filename, args=(), optimized=0, klass=None):
  317.         self.super_init()
  318.         self.name = name
  319.         self.filename = filename
  320.         self.docstring = None
  321.         self.args = args # XXX
  322.         self.argcount = getArgCount(args)
  323.         self.klass = klass
  324.         if optimized:
  325.             self.flags = CO_OPTIMIZED | CO_NEWLOCALS
  326.         else:
  327.             self.flags = 0
  328.         self.consts = []
  329.         self.names = []
  330.         # Free variables found by the symbol table scan, including
  331.         # variables used only in nested scopes, are included here.
  332.         self.freevars = []
  333.         self.cellvars = []
  334.         # The closure list is used to track the order of cell
  335.         # variables and free variables in the resulting code object.
  336.         # The offsets used by LOAD_CLOSURE/LOAD_DEREF refer to both
  337.         # kinds of variables.
  338.         self.closure = []
  339.         self.varnames = list(args) or []
  340.         for i in range(len(self.varnames)):
  341.             var = self.varnames[i]
  342.             if isinstance(var, TupleArg):
  343.                 self.varnames[i] = var.getName()
  344.         self.stage = RAW
  345.  
  346.     def setDocstring(self, doc):
  347.         self.docstring = doc
  348.  
  349.     def setFlag(self, flag):
  350.         self.flags = self.flags | flag
  351.         if flag == CO_VARARGS:
  352.             self.argcount = self.argcount - 1
  353.  
  354.     def checkFlag(self, flag):
  355.         if self.flags & flag:
  356.             return 1
  357.  
  358.     def setFreeVars(self, names):
  359.         self.freevars = list(names)
  360.  
  361.     def setCellVars(self, names):
  362.         self.cellvars = names
  363.  
  364.     def getCode(self):
  365.         """Get a Python code object"""
  366.         assert self.stage == RAW
  367.         self.computeStackDepth()
  368.         self.flattenGraph()
  369.         assert self.stage == FLAT
  370.         self.convertArgs()
  371.         assert self.stage == CONV
  372.         self.makeByteCode()
  373.         assert self.stage == DONE
  374.         return self.newCodeObject()
  375.  
  376.     def dump(self, io=None):
  377.         if io:
  378.             save = sys.stdout
  379.             sys.stdout = io
  380.         pc = 0
  381.         for t in self.insts:
  382.             opname = t[0]
  383.             if opname == "SET_LINENO":
  384.                 print
  385.             if len(t) == 1:
  386.                 print "\t", "%3d" % pc, opname
  387.                 pc = pc + 1
  388.             else:
  389.                 print "\t", "%3d" % pc, opname, t[1]
  390.                 pc = pc + 3
  391.         if io:
  392.             sys.stdout = save
  393.  
  394.     def computeStackDepth(self):
  395.         """Compute the max stack depth.
  396.  
  397.         Approach is to compute the stack effect of each basic block.
  398.         Then find the path through the code with the largest total
  399.         effect.
  400.         """
  401.         depth = {}
  402.         exit = None
  403.         for b in self.getBlocks():
  404.             depth[b] = findDepth(b.getInstructions())
  405.  
  406.         seen = {}
  407.  
  408.         def max_depth(b, d):
  409.             if seen.has_key(b):
  410.                 return d
  411.             seen[b] = 1
  412.             d = d + depth[b]
  413.             children = b.get_children()
  414.             if children:
  415.                 return max([max_depth(c, d) for c in children])
  416.             else:
  417.                 if not b.label == "exit":
  418.                     return max_depth(self.exit, d)
  419.                 else:
  420.                     return d
  421.  
  422.         self.stacksize = max_depth(self.entry, 0)
  423.  
  424.     def flattenGraph(self):
  425.         """Arrange the blocks in order and resolve jumps"""
  426.         assert self.stage == RAW
  427.         self.insts = insts = []
  428.         pc = 0
  429.         begin = {}
  430.         end = {}
  431.         for b in self.getBlocksInOrder():
  432.             begin[b] = pc
  433.             for inst in b.getInstructions():
  434.                 insts.append(inst)
  435.                 if len(inst) == 1:
  436.                     pc = pc + 1
  437.                 elif inst[0] != "SET_LINENO":
  438.                     # arg takes 2 bytes
  439.                     pc = pc + 3
  440.             end[b] = pc
  441.         pc = 0
  442.         for i in range(len(insts)):
  443.             inst = insts[i]
  444.             if len(inst) == 1:
  445.                 pc = pc + 1
  446.             elif inst[0] != "SET_LINENO":
  447.                 pc = pc + 3
  448.             opname = inst[0]
  449.             if self.hasjrel.has_elt(opname):
  450.                 oparg = inst[1]
  451.                 offset = begin[oparg] - pc
  452.                 insts[i] = opname, offset
  453.             elif self.hasjabs.has_elt(opname):
  454.                 insts[i] = opname, begin[inst[1]]
  455.         self.stage = FLAT
  456.  
  457.     hasjrel = misc.Set()
  458.     for i in dis.hasjrel:
  459.         hasjrel.add(dis.opname[i])
  460.     hasjabs = misc.Set()
  461.     for i in dis.hasjabs:
  462.         hasjabs.add(dis.opname[i])
  463.  
  464.     def convertArgs(self):
  465.         """Convert arguments from symbolic to concrete form"""
  466.         assert self.stage == FLAT
  467.         self.consts.insert(0, self.docstring)
  468.         self.sort_cellvars()
  469.         for i in range(len(self.insts)):
  470.             t = self.insts[i]
  471.             if len(t) == 2:
  472.                 opname, oparg = t
  473.                 conv = self._converters.get(opname, None)
  474.                 if conv:
  475.                     self.insts[i] = opname, conv(self, oparg)
  476.         self.stage = CONV
  477.  
  478.     def sort_cellvars(self):
  479.         """Sort cellvars in the order of varnames and prune from freevars.
  480.         """
  481.         cells = {}
  482.         for name in self.cellvars:
  483.             cells[name] = 1
  484.         self.cellvars = [name for name in self.varnames
  485.                          if cells.has_key(name)]
  486.         for name in self.cellvars:
  487.             del cells[name]
  488.         self.cellvars = self.cellvars + cells.keys()
  489.         self.closure = self.cellvars + self.freevars
  490.  
  491.     def _lookupName(self, name, list):
  492.         """Return index of name in list, appending if necessary
  493.  
  494.         This routine uses a list instead of a dictionary, because a
  495.         dictionary can't store two different keys if the keys have the
  496.         same value but different types, e.g. 2 and 2L.  The compiler
  497.         must treat these two separately, so it does an explicit type
  498.         comparison before comparing the values.
  499.         """
  500.         t = type(name)
  501.         for i in range(len(list)):
  502.             if t == type(list[i]) and list[i] == name:
  503.                 return i
  504.         end = len(list)
  505.         list.append(name)
  506.         return end
  507.  
  508.     _converters = {}
  509.     def _convert_LOAD_CONST(self, arg):
  510.         if hasattr(arg, 'getCode'):
  511.             arg = arg.getCode()
  512.         return self._lookupName(arg, self.consts)
  513.  
  514.     def _convert_LOAD_FAST(self, arg):
  515.         self._lookupName(arg, self.names)
  516.         return self._lookupName(arg, self.varnames)
  517.     _convert_STORE_FAST = _convert_LOAD_FAST
  518.     _convert_DELETE_FAST = _convert_LOAD_FAST
  519.  
  520.     def _convert_LOAD_NAME(self, arg):
  521.         if self.klass is None:
  522.             self._lookupName(arg, self.varnames)
  523.         return self._lookupName(arg, self.names)
  524.  
  525.     def _convert_NAME(self, arg):
  526.         if self.klass is None:
  527.             self._lookupName(arg, self.varnames)
  528.         return self._lookupName(arg, self.names)
  529.     _convert_STORE_NAME = _convert_NAME
  530.     _convert_DELETE_NAME = _convert_NAME
  531.     _convert_IMPORT_NAME = _convert_NAME
  532.     _convert_IMPORT_FROM = _convert_NAME
  533.     _convert_STORE_ATTR = _convert_NAME
  534.     _convert_LOAD_ATTR = _convert_NAME
  535.     _convert_DELETE_ATTR = _convert_NAME
  536.     _convert_LOAD_GLOBAL = _convert_NAME
  537.     _convert_STORE_GLOBAL = _convert_NAME
  538.     _convert_DELETE_GLOBAL = _convert_NAME
  539.  
  540.     def _convert_DEREF(self, arg):
  541.         self._lookupName(arg, self.names)
  542.         self._lookupName(arg, self.varnames)
  543.         return self._lookupName(arg, self.closure)
  544.     _convert_LOAD_DEREF = _convert_DEREF
  545.     _convert_STORE_DEREF = _convert_DEREF
  546.  
  547.     def _convert_LOAD_CLOSURE(self, arg):
  548.         self._lookupName(arg, self.varnames)
  549.         return self._lookupName(arg, self.closure)
  550.  
  551.     _cmp = list(dis.cmp_op)
  552.     def _convert_COMPARE_OP(self, arg):
  553.         return self._cmp.index(arg)
  554.  
  555.     # similarly for other opcodes...
  556.  
  557.     for name, obj in locals().items():
  558.         if name[:9] == "_convert_":
  559.             opname = name[9:]
  560.             _converters[opname] = obj
  561.     del name, obj, opname
  562.  
  563.     def makeByteCode(self):
  564.         assert self.stage == CONV
  565.         self.lnotab = lnotab = LineAddrTable()
  566.         for t in self.insts:
  567.             opname = t[0]
  568.             if len(t) == 1:
  569.                 lnotab.addCode(self.opnum[opname])
  570.             else:
  571.                 oparg = t[1]
  572.                 if opname == "SET_LINENO":
  573.                     lnotab.nextLine(oparg)
  574.                     continue
  575.                 hi, lo = twobyte(oparg)
  576.                 try:
  577.                     lnotab.addCode(self.opnum[opname], lo, hi)
  578.                 except ValueError:
  579.                     print opname, oparg
  580.                     print self.opnum[opname], lo, hi
  581.                     raise
  582.         self.stage = DONE
  583.  
  584.     opnum = {}
  585.     for num in range(len(dis.opname)):
  586.         opnum[dis.opname[num]] = num
  587.     del num
  588.  
  589.     def newCodeObject(self):
  590.         assert self.stage == DONE
  591.         if (self.flags & CO_NEWLOCALS) == 0:
  592.             nlocals = 0
  593.         else:
  594.             nlocals = len(self.varnames)
  595.         argcount = self.argcount
  596.         if self.flags & CO_VARKEYWORDS:
  597.             argcount = argcount - 1
  598.         return new.code(argcount, nlocals, self.stacksize, self.flags,
  599.                         self.lnotab.getCode(), self.getConsts(),
  600.                         tuple(self.names), tuple(self.varnames),
  601.                         self.filename, self.name, self.lnotab.firstline,
  602.                         self.lnotab.getTable(), tuple(self.freevars),
  603.                         tuple(self.cellvars))
  604.  
  605.     def getConsts(self):
  606.         """Return a tuple for the const slot of the code object
  607.  
  608.         Must convert references to code (MAKE_FUNCTION) to code
  609.         objects recursively.
  610.         """
  611.         l = []
  612.         for elt in self.consts:
  613.             if isinstance(elt, PyFlowGraph):
  614.                 elt = elt.getCode()
  615.             l.append(elt)
  616.         return tuple(l)
  617.  
  618. def isJump(opname):
  619.     if opname[:4] == 'JUMP':
  620.         return 1
  621.  
  622. class TupleArg:
  623.     """Helper for marking func defs with nested tuples in arglist"""
  624.     def __init__(self, count, names):
  625.         self.count = count
  626.         self.names = names
  627.     def __repr__(self):
  628.         return "TupleArg(%s, %s)" % (self.count, self.names)
  629.     def getName(self):
  630.         return ".%d" % self.count
  631.  
  632. def getArgCount(args):
  633.     argcount = len(args)
  634.     if args:
  635.         for arg in args:
  636.             if isinstance(arg, TupleArg):
  637.                 numNames = len(misc.flatten(arg.names))
  638.                 argcount = argcount - numNames
  639.     return argcount
  640.  
  641. def twobyte(val):
  642.     """Convert an int argument into high and low bytes"""
  643.     assert isinstance(val, int)
  644.     return divmod(val, 256)
  645.  
  646. class LineAddrTable:
  647.     """lnotab
  648.  
  649.     This class builds the lnotab, which is documented in compile.c.
  650.     Here's a brief recap:
  651.  
  652.     For each SET_LINENO instruction after the first one, two bytes are
  653.     added to lnotab.  (In some cases, multiple two-byte entries are
  654.     added.)  The first byte is the distance in bytes between the
  655.     instruction for the last SET_LINENO and the current SET_LINENO.
  656.     The second byte is offset in line numbers.  If either offset is
  657.     greater than 255, multiple two-byte entries are added -- see
  658.     compile.c for the delicate details.
  659.     """
  660.  
  661.     def __init__(self):
  662.         self.code = []
  663.         self.codeOffset = 0
  664.         self.firstline = 0
  665.         self.lastline = 0
  666.         self.lastoff = 0
  667.         self.lnotab = []
  668.  
  669.     def addCode(self, *args):
  670.         for arg in args:
  671.             self.code.append(chr(arg))
  672.         self.codeOffset = self.codeOffset + len(args)
  673.  
  674.     def nextLine(self, lineno):
  675.         if self.firstline == 0:
  676.             self.firstline = lineno
  677.             self.lastline = lineno
  678.         else:
  679.             # compute deltas
  680.             addr = self.codeOffset - self.lastoff
  681.             line = lineno - self.lastline
  682.             # Python assumes that lineno always increases with
  683.             # increasing bytecode address (lnotab is unsigned char).
  684.             # Depending on when SET_LINENO instructions are emitted
  685.             # this is not always true.  Consider the code:
  686.             #     a = (1,
  687.             #          b)
  688.             # In the bytecode stream, the assignment to "a" occurs
  689.             # after the loading of "b".  This works with the C Python
  690.             # compiler because it only generates a SET_LINENO instruction
  691.             # for the assignment.
  692.             if line >= 0:
  693.                 push = self.lnotab.append
  694.                 while addr > 255:
  695.                     push(255); push(0)
  696.                     addr -= 255
  697.                 while line > 255:
  698.                     push(addr); push(255)
  699.                     line -= 255
  700.                     addr = 0
  701.                 if addr > 0 or line > 0:
  702.                     push(addr); push(line)
  703.                 self.lastline = lineno
  704.                 self.lastoff = self.codeOffset
  705.  
  706.     def getCode(self):
  707.         return ''.join(self.code)
  708.  
  709.     def getTable(self):
  710.         return ''.join(map(chr, self.lnotab))
  711.  
  712. class StackDepthTracker:
  713.     # XXX 1. need to keep track of stack depth on jumps
  714.     # XXX 2. at least partly as a result, this code is broken
  715.  
  716.     def findDepth(self, insts, debug=0):
  717.         depth = 0
  718.         maxDepth = 0
  719.         for i in insts:
  720.             opname = i[0]
  721.             if debug:
  722.                 print i,
  723.             delta = self.effect.get(opname, None)
  724.             if delta is not None:
  725.                 depth = depth + delta
  726.             else:
  727.                 # now check patterns
  728.                 for pat, pat_delta in self.patterns:
  729.                     if opname[:len(pat)] == pat:
  730.                         delta = pat_delta
  731.                         depth = depth + delta
  732.                         break
  733.                 # if we still haven't found a match
  734.                 if delta is None:
  735.                     meth = getattr(self, opname, None)
  736.                     if meth is not None:
  737.                         depth = depth + meth(i[1])
  738.             if depth > maxDepth:
  739.                 maxDepth = depth
  740.             if debug:
  741.                 print depth, maxDepth
  742.         return maxDepth
  743.  
  744.     effect = {
  745.         'POP_TOP': -1,
  746.         'DUP_TOP': 1,
  747.         'LIST_APPEND': -2,
  748.         'SLICE+1': -1,
  749.         'SLICE+2': -1,
  750.         'SLICE+3': -2,
  751.         'STORE_SLICE+0': -1,
  752.         'STORE_SLICE+1': -2,
  753.         'STORE_SLICE+2': -2,
  754.         'STORE_SLICE+3': -3,
  755.         'DELETE_SLICE+0': -1,
  756.         'DELETE_SLICE+1': -2,
  757.         'DELETE_SLICE+2': -2,
  758.         'DELETE_SLICE+3': -3,
  759.         'STORE_SUBSCR': -3,
  760.         'DELETE_SUBSCR': -2,
  761.         # PRINT_EXPR?
  762.         'PRINT_ITEM': -1,
  763.         'RETURN_VALUE': -1,
  764.         'YIELD_VALUE': -1,
  765.         'EXEC_STMT': -3,
  766.         'BUILD_CLASS': -2,
  767.         'STORE_NAME': -1,
  768.         'STORE_ATTR': -2,
  769.         'DELETE_ATTR': -1,
  770.         'STORE_GLOBAL': -1,
  771.         'BUILD_MAP': 1,
  772.         'COMPARE_OP': -1,
  773.         'STORE_FAST': -1,
  774.         'IMPORT_STAR': -1,
  775.         'IMPORT_NAME': -1,
  776.         'IMPORT_FROM': 1,
  777.         'LOAD_ATTR': 0, # unlike other loads
  778.         # close enough...
  779.         'SETUP_EXCEPT': 3,
  780.         'SETUP_FINALLY': 3,
  781.         'FOR_ITER': 1,
  782.         'WITH_CLEANUP': -1,
  783.         }
  784.     # use pattern match
  785.     patterns = [
  786.         ('BINARY_', -1),
  787.         ('LOAD_', 1),
  788.         ]
  789.  
  790.     def UNPACK_SEQUENCE(self, count):
  791.         return count-1
  792.     def BUILD_TUPLE(self, count):
  793.         return -count+1
  794.     def BUILD_LIST(self, count):
  795.         return -count+1
  796.     def CALL_FUNCTION(self, argc):
  797.         hi, lo = divmod(argc, 256)
  798.         return -(lo + hi * 2)
  799.     def CALL_FUNCTION_VAR(self, argc):
  800.         return self.CALL_FUNCTION(argc)-1
  801.     def CALL_FUNCTION_KW(self, argc):
  802.         return self.CALL_FUNCTION(argc)-1
  803.     def CALL_FUNCTION_VAR_KW(self, argc):
  804.         return self.CALL_FUNCTION(argc)-2
  805.     def MAKE_FUNCTION(self, argc):
  806.         return -argc
  807.     def MAKE_CLOSURE(self, argc):
  808.         # XXX need to account for free variables too!
  809.         return -argc
  810.     def BUILD_SLICE(self, argc):
  811.         if argc == 2:
  812.             return -1
  813.         elif argc == 3:
  814.             return -2
  815.     def DUP_TOPX(self, argc):
  816.         return argc
  817.  
  818. findDepth = StackDepthTracker().findDepth
  819.